package easy;

public class Solution_LCP_28 {

    public int purchasePlans(int[] nums, int target) {
        int[] array = new int[100001];
        for (int num : nums) {
            array[num]++;
        }
        for (int i = 1; i < array.length; i++) {
            array[i] += array[i - 1];
        }
        long count = 0;
        for (int num : nums) {
            int sub = target - num;
            if (sub >= 0) {
                int offset = 0;
                if (num <= sub) {
                    offset = -1;
                }
                count += (array[sub] + offset);
            }
        }
        return (int) ((count >> 1) % 1000000007);
    }

    public static void main(String[] args) {
        Solution_LCP_28 model = new Solution_LCP_28();
//        System.out.println(model.purchasePlans(new int[]{2, 5, 3, 5}, 6));
        System.out.println(model.purchasePlans(new int[]{2, 2, 1, 9}, 10));
    }
}
